package com.mid;

/**
 * Created by Lxk on 2019/6/3.
 */
public class Solution143 {
    /**
     * 首先拆分，然后后半部分转置，然后再合并
     * 1->2->3->4_
     * 1->2->3->4->5_
     * @param head
     */
    public void reorderList(ListNode head) {
        if(head==null) {
            return;
        }
        //找中点
        ListNode slower = new ListNode(0);
        slower.next = head;
        ListNode faster = head;
        while(faster!=null){
            faster = faster.next;
            slower = slower.next;
            if(faster!=null){
                faster = faster.next;
            }
        }
        // 拆分
        ListNode partCur2 = slower.next;
        slower.next = null;
        partCur2 = reverseList(partCur2);
        ListNode partCur = head;
        while(partCur2!=null){
            ListNode next = partCur.next;
            ListNode next2 = partCur2.next;
            partCur.next = partCur2;
            partCur2.next = next;
            partCur = next;
            partCur2 = next2;
        }
    }

    private ListNode reverseList(ListNode head){
        if(head==null){
            return null;
        }
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

}
